package com.sakura.二分查找;

/**
 * 设 x=nums[mid] 是现在二分取到的数。
 *
 * 我们需要判断 x 和数组最小值的位置关系，谁在左边，谁在右边？
 *
 * 把 x 与最后一个数 nums[n−1] 比大小：
 *
 * 如果 x>nums[n−1]，那么可以推出以下结论：
 * nums 一定被分成左右两个递增段；
 * 第一段的所有元素均大于第二段的所有元素；
 * x 在第一段。
 * 最小值在第二段。
 * 所以 x 一定在最小值的左边。
 * 如果 x≤nums[n−1]，那么 x 一定在第二段。（或者 nums 就是递增数组，此时只有一段。）
 * x 要么是最小值，要么在最小值右边。
 * 所以，只需要比较 x 和 nums[n−1] 的大小关系，就间接地知道了 x 和数组最小值的位置关系，从而不断地缩小数组最小值所在位置的范围，二分找到数组最小值。
 *
 * 作者：灵茶山艾府
 * 链接：https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/solutions/1987499/by-endlesscheng-owgd/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
public class Code153_寻找旋转排序数组中的最小值 {

    public static void main(String[] args) {
        int[] nums = {3,1,2};
        System.out.println(new Code153_寻找旋转排序数组中的最小值().findMin(nums));
    }


    public int findMin(int[] nums) {
        int left = -1;
        int right = nums.length - 1;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return nums[right];
    }
    public int findMin1(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = n - 1;
        while (left < right) {
            int mid = (right + left) >>> 1;
            if (nums[mid] > nums[n - 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}
